/**
 * JavaScript快速排序实现
 * @param {*} arr 
 * @returns 
 */
function quickSort(arr) {
    if (arr.length < 2) {
        return arr;
    }

    const pivotIndex = Math.floor(arr.length / 2);
    const pivot = arr.splice(pivotIndex, 1)[0];//改变了原始序列
    const left = [];
    const right = [];

    for (let i = 0; i < arr.length; i++) {
        if (arr[i] < pivot) {
            left.push(arr[i]);
        } else {
            right.push(arr[i]);
        }
    }

    return quickSort(left).concat([pivot], quickSort(right));
}
